def inplace_count_sort(A, k):
    n = len(A)
    C = [0] * (k + 1)
    D = [0] * (k + 1)
    for a in A:
        C[a] += 1
    C[0] -= 1 #index start from count[that number]-1
    for i in xrange(1, k + 1):
        C[i] += C[i - 1]
    D = C[:] #(D[x],D[x]] are the numbers that are done
    for j in xrange(n-1, -1, -1):
        if D[A[j]] <= j <= C[A[j]]:
            if j == D[A[j]]:
                D[A[j]] -= 1
            continue
        x = A[j]; i = D[x]
        A[j] = None #dig a hole
        while A[i] is not None:
            D[x] -= 1
            x, A[i] = A[i], x
            i = D[x]
        A[i] = x #fill the hole
    return A

if __name__ == '__main__':
    A = [7,8,9,1,3,4,5,5,5,6,2,0,0,3,3,2,2,2,1,1,1]
    print "A: ", A
    B = inplace_count_sort(A,10)
    print "B: ", B
